//
//  main.cpp
//  二叉排序树
//
//  Created by 刘晨 on 2018/12/19.
//  Copyright © 2018 刘晨. All rights reserved.
//
/*
二叉排序树就是根节点的左子树比他小，右子树比他大；

注意： ******************************************************
指针的指向要规定好，不能让指针乱指，这样会造成没有必要的麻烦。有的时候，逻辑上没有问题，但是就是输出有问题，那可能就是指针指向有问题，比如我遇到的问题如下：
1；首先就是在删除5这个结点的时候，逻辑上没有问题，结果输出一直在1，3，4，10，中循环，问题就是出现在findMIn中父结点的指向有问题，删除这个结点之后没有设置为NULL，从而就导致了这样的问题。
*/

#include <iostream>
using namespace std;
typedef struct node{
int data;
node* rchild;
node* lchild;
}node;

class Tree{
private:
node * head;//树的头结点
node * seachx(node * t,int data);//私有递归的查询
void insertx(node *& t,int data);//私有递归的插入;

void inorder(node*p);// 中序遍历
node* findMin(node*p,node*parent);//找删除的结点的左子树中的最大值,参数一，从那个结点开始，参数二，这个结点的父结点
bool isLeaf(node *p);//看是不是叶子结点
bool deleteNode(node *parnet,node*p,int data,int direction);//私有删除结点 参数一，从那个结点开始，参数二，这个结点的父结点，参数三 要删除的数据，参数四，位于哪个子树，左子树用1表示，右子树用0来表示。


bool isHaveLeftChild(node *p);
public:
void searchTree(int data);//公有函数调用私有插入，寻找结点
void inserTree(int *a,int length);//参数一：将数组传进来，参数二，数组的长度；。。插入结点。
void deleteTree(int data);//删除结点.
void inorderTree();
Tree();
};
bool Tree::isHaveLeftChild(node *p){
if(p ->lchild != NULL && p->rchild ==NULL){
    return true;
}
return false;
}

Tree::Tree(){
head = NULL;
}
/*
寻找就是便利二叉树，寻找
*/
node* Tree:: seachx(node *t , int data ){
if (t == NULL) {
    return  NULL;
}
else{
    if(t->data == data) return t;
    if(t->data < data) t = seachx(t->rchild, data);
    if(t->data > data) t = seachx(t->lchild, data);
}
return t;
}
/*
插入其实就是不断的插入叶子结点，先找到叶子结点之后再创建结点，然后插入，大的放在右边，小的放在左边。
参数一是引用的指针，这就就不需要返回值。直接就相连了。
*/
void Tree::insertx(node *&t , int data   ){
if(t == NULL){
    t = new node;
    t->lchild = t->rchild = NULL;
    t->data = data;
    
}
else{
    if (t->data <data) insertx(t->rchild, data);
    if (t -> data > data) insertx(t->lchild, data);
}

}

void Tree::searchTree(int data){
node*p = head;
p =  seachx(p, data);
cout<<p<<endl;
cout<<p->data;
}
void Tree::inserTree(int* a,int length){
for (int i =0; i<length; i++) {
    insertx(head, a[i] );
}
}
void Tree::inorder(node *p){
if (p == NULL){
    return;
}
else{
    inorder(p->lchild);
    cout<<p->data<<"\n";
    inorder(p->rchild);
}
}
void Tree::inorderTree(){
node*p = head;
inorder(p);

}

node* Tree::findMin(node *p,node*parent){
cout<<p->data<<":"<<parent->data<<endl;
if(p->lchild == NULL){
    //即就是找到了这个结点，然后将父结点的左子树设置为NULL
    parent->lchild=NULL;
    return p;
}
else{
    //否则就继续找
    p = findMin(p->lchild, p);
}
return p;
}


bool Tree::isLeaf(node *p){

if(p->lchild == NULL && p->rchild == NULL){
    return true;
}
return false;
}


/*
返回值为bool是为了，判断有没有找到，要是左子树没有找到就继续去找右子树。
*/
bool Tree::deleteNode(node *parnet,node*p,int data,int diretcion){
if (p == NULL) {
    //设置终止条件。
    return false;
}
else{
    cout<<"parent"<<parnet->data<<endl;
    cout<<"delete  NOde "<<p->data<<endl;
    if(p->data == data){
        if(isLeaf( p) == true){
            //               这个结点是叶子结点
            if(diretcion == 1) {
                //左边
                parnet->lchild = NULL;delete p;
            }
            if(diretcion == 0) {
                //右边
                parnet->rchild = NULL;delete p;
            }
        }
        
        
        if(isHaveLeftChild(p) == true){
            //只有左子树
            if(diretcion == 1) {
                parnet->lchild = p->lchild;delete p;
            }
            if(diretcion == 0) {
                parnet->rchild = p->lchild;delete p;
            }
        }
        else {
            //有右子树
            node *t = findMin(p->rchild,p->rchild);//找到最替换的结点
            cout<<t->data<<endl;
            cout<<parnet->data<<endl;
            if(diretcion == 1) {
                if(p->rchild->lchild == NULL){
                    //删除的结点的右子树的左子树 没有。
                    parnet->lchild = t;
                    cout<<p->data<<endl;
                    t->rchild= p->rchild->rchild;
                    t->lchild = p->lchild;
                    delete p;
                }
                else{
                    //要删除的结点的右子树有左子树。
                    parnet->lchild = t;
                    cout<<p->data<<endl;
                    cout<<p->rchild->data<<endl;
                    t->rchild= p->rchild;
                    t->lchild = p->lchild;
                    delete p;
                }
            }
            if(diretcion == 0) {
                if(p->rchild->lchild == NULL){
                    parnet->rchild = t;
                    t->rchild= p->rchild->rchild;
                    t->lchild = p->lchild;
                    delete p;
                }
                else{
                    parnet->rchild = t;
                    t->lchild = p->lchild;
                    t->rchild = p->rchild;
                    delete p;
                }
            }
            
        }
    }
    if( data > p->data){
        deleteNode(p, p->rchild, data, 0);
    }
    if(data < p->data){
        deleteNode(p, p->lchild, data, 1);
    }
    return true;
}

}
void Tree::deleteTree(int data){
if (true == deleteNode(head, head, data, 1)){
    return;
}
else{
    deleteNode(head, head, data, 1);
}
}
int main(){
Tree a ;
int b[] = {28,5,4,16,3,1,29,19,17};
a.inserTree(b,9);
a.inorderTree();
a.searchTree(1);
a.deleteTree(3);
cout<<"删除后的结点如下：\n";
a.inorderTree();
cout<<endl;
return 1;
}











